home *** CD-ROM | disk | FTP | other *** search
/ 1,000+ Great Games / 1_1000 Games.iso / DOOM / ZEN096.ZIP / BSPINFO.DOC next >
Encoding:
Text File  |  1995-11-29  |  2.9 KB  |  58 lines
  1.  
  2.                  BSPInfo Version 1.01 by Marc Rousseau
  3.  
  4.     During the development of ZenNode, I often wondered what was going on
  5. with the BSP structures that were being built.  Was this algorithm doing 
  6. better than that one?  How balanced is the tree?  How deep is it going? ...
  7. BSPInfo grew out of the tool used to see what was going on.  It reports
  8. statistics to describe the BSP tree.  It can be used to give you a feel of
  9. how particular Node builders are performing.
  10.  
  11.     The following is a brief description of each of the values displayed by
  12. BSPInfo.
  13.  
  14.     Depth    The maximum depth of the BSP tree.  The deeper the tree, the
  15.         more work DOOM has to do to update the display.  A smaller
  16.                 value means that, on average, DOOM will have fewer NODES to
  17.                 traverse when updating the screen.
  18.  
  19.     FOM        ( Figure of Merit )  This is an attempt to measure the 
  20.         'balance' of the tree.  Each node with both a right and left
  21.         child or no children is considered balanced.  The FOM value
  22.         is a ratio of balanced nodes to the overall number of nodes.
  23.         An FOM of 1.000 indicates perfect binary tree.  This will 
  24.         *VERY RARELY* occur, since it requires a number of nodes that
  25.         is an exact power of 2 and every node being balanced.
  26.  
  27.     Balance     The percentage of nodes to the left and right of the root
  28.                 node.  Generally, a more balanced tree is preferable to a less
  29.                 balanced tree, since, the average depth for any node is likely
  30.                 to be smaller.  ( This actually is an indication of how well
  31.                 the node builder chose it's first partition. )
  32.  
  33.     Splits    How many times the Node builder had to split segments to 
  34.         fit everything into the tree.  There are no hard rules saying
  35.         that splits are bad, however fewer is generally better.
  36.  
  37.     Diagonals    The number of BSP partition lines chosen that were diagonal.
  38.         The DOOM rendering engine runs much faster when the partition
  39.         lines are either vertical or horizontal.  Generally the fewer
  40.         diagonals the better.
  41.  
  42.     Nodes    Number of NODES in the map.
  43.     Segs    Number of SEGS in the map.
  44.  
  45.  
  46. IMPORTANT:
  47.  
  48.     None of these figures are meant to imply that one Node builder is better
  49. (or worse) than another.  They are simply designed to describe the type of
  50. BSP trees being built.  Some favor shallow tree depths, others attempt to 
  51. reduce splits, others favor reducing diagonals.  No one value should be viewed
  52. as more important than the others.  In general, if a Node builder builds a 
  53. BSP tree with all values significantly lower, except FOM, than other Node 
  54. builders, it most likely means that that level will play slightly faster in 
  55. DOOM but is no more or less 'correct' than any other Node builder.  Of course
  56. these numbers aren't important.  The only thing that is important is that
  57. the BSP tree created works correctly under DOOM.
  58.